package com.sise.Array;

/**
 *      75. 颜色分类
 *
 *      给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
 *      此题中，我们使用整数 0、1 和 2 分别表示红色、白色和蓝色。
 *
 *      输入：nums = [2,0,2,1,1,0]
 *      输出：[0,0,1,1,2,2]
 */
public class _75_sortColors {
    public void sortColors(int[] nums) {

        int length = nums.length;
        if (length < 2) return;

        // 这里将数组分为三个区间 [0 - zero - i(two) - len-1]
        // all in [0, zero) = 0
        // all in [zero, i) = 1
        // all in [two, len - 1] = 2

        int zero = 0;                           // zero 代表 [0，zero) 区间中的数值都为 0

        int two = length;                       // two 代表 [two，len] 区间中的数值都为 2
        int i = 0;                              // i 是移动的，通过它进而判断当前 num[i] 是否需要移动

        while (i < two) {                       // 当 i == two，那么说明已经将所有数字都转换好了
            if (nums[i] == 0) {                 // 如果 num[i] = 0，那么就交换 i 和 zero 的位置，保证为 0 的数字都能够到达数组的左边
                swap(nums, i, zero);
                zero++;
                i++;
            } else if (nums[i] == 1) {          // 如果 num[i] = 1，不需要对其移动，在原位置即可，我们只移动 0 和 2 而已
                i++;
            } else {                            // 如果 num[i] = 2，那么将后面的 two--，同时交换 i 和 two，目的是将 num[i] 放到右边
                two--;                          // 这里没有对其进行 i++，因为对移动后的数字 num[i]，不确定是否还需要移动，故此还需要对其进行遍历判断
                swap(nums, i, two);
            }
        }
    }

    private void swap(int[] nums, int index1, int index2) {
        int temp = nums[index1];
        nums[index1] = nums[index2];
        nums[index2] = temp;
    }
}
